#pragma once

namespace Melting
{
namespace Parallel
{
	//--------------------------------------------------------------------------------------------------------------------
	template< class T >
    class LockFreeStack
    { 

    public :

		//--------------------------------------------------------------------------------------------------------
		struct Node
		{			
			T		mValue;
			Node*	mpNext;
		};

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
        LockFreeStack( void )
		{ 			
			STATIC_ASSERT( sizeof(Node*) == 4, LockFreeStack_works_only_with_32bits_pointers );

			mHead.mValue = 0;
        }

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
        ~LockFreeStack( void )
        { 
			// delete every node in the list
        }

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
		/// Push a whole list into the stack, where the first item in the list is _pFirstNode, and the last is _pLastNode
		FORCEINLINE void PushList( Node* _pFirstNode, Node* _pLastNode, UINT32 _iListSize )
		{ 
			//------------------------
			// precondition
			MB_ASSERT( nullptr != _pFirstNode, "Trying to Push a nullptr as first node of the list! That's forbidden.\n" );
			MB_ASSERT( nullptr != _pLastNode, "Trying to Push a nullptr as last node of the list! That's forbidden.\n" );
			MB_ASSERT( 0 < _iListSize, "Trying to Push an empty List ! That's forbidden.\n" );
			//------------------------

			Head	oldHead;
			Head	newHead;

			while( true )
			{
				oldHead.mValue = mHead.mValue;

				newHead.miSequence	= oldHead.miSequence + 1;
				newHead.miSize		= oldHead.miSize + _iListSize;
				newHead.mpNext		= _pFirstNode;

				_pLastNode->mpNext = oldHead.mpNext;

				if( oldHead.mValue == AtomicCompareAndSwap64bits( &mHead.mValue, newHead.mValue, oldHead.mValue ) )
				{
					// success
					return;
				}
			}   
		}

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
		/// Push a user allocated Node onto the stack
		FORCEINLINE void Push( Node* _pNode )
		{ 
			//------------------------
			// precondition
			MB_ASSERT( nullptr != _pNode, "Trying to Push a nullptr ! That's forbidden.\n" );
			//------------------------

			Head	oldHead;
			Head	newHead;

			while( true )
			{
				oldHead.mValue = mHead.mValue;

				newHead.miSequence	= oldHead.miSequence + 1;
				newHead.miSize		= oldHead.miSize + 1;
				newHead.mpNext		= _pNode;

				_pNode->mpNext = oldHead.mpNext;

				if( oldHead.mValue == AtomicCompareAndSwap64bits( &mHead.mValue, newHead.mValue, oldHead.mValue ) )
				{
					// success
					return;
				}
			}   
		}

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
		/// Pop a user allocated Node from the top of the stack
		FORCEINLINE Node* Pop( void )
		{  
			Head	oldHead;
			Head	newHead;
			
			Node*	pHeadNode;

			while( true )
			{
				oldHead.mValue = mHead.mValue;

				// if there is something to pop, try it !
				if( 0 < oldHead.miSize )
				{
					pHeadNode = oldHead.mpNext;

					newHead.miSequence	= oldHead.miSequence + 1;
					newHead.miSize		= oldHead.miSize - 1;
					newHead.mpNext		= pHeadNode->mpNext; // since we tested the miSize > 0, we are sure that oldHeap.mpNext is != nullptr

					if( oldHead.mValue == AtomicCompareAndSwap64bits( &mHead.mValue, newHead.mValue, oldHead.mValue ) )
					{
						// success
						return pHeadNode;
					}
				}
				else
				{
					return nullptr;
				}
			}   
		} 

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
		/// Detach the whole content of the stack, and returns it as a singly linked list
		FORCEINLINE Node* DetachAll( void )
		{  
			Head	oldHead;
			Head	newHead;
			
			Node*	pHeadNode;

			while( true )
			{
				oldHead.mValue = mHead.mValue;

				newHead.miSequence	= oldHead.miSequence + 1;
				newHead.miSize		= 0;
				newHead.mpNext		= nullptr;

				pHeadNode = oldHead.mpNext;

				if( oldHead.mValue == AtomicCompareAndSwap64bits( &mHead.mValue, newHead.mValue, oldHead.mValue ) )
				{
					// success
					return pHeadNode;
				}
			}   
		} 

		//--------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------
		/// Current number of items in the stack
		UINT32  GetSize( void ) const
        {
            return mHead.miSize;
        } 

    private:

		struct Head
		{
			union
			{
				struct 
				{
					Node*	mpNext;
					UINT16	miSize;
					UINT16	miSequence;
				};			
				volatile INT64 mValue;
			};
		};
		typedef UBYTE	CacheLinePadding[ CACHE_LINE_SIZE ];
 
		//CacheLinePadding		pad1;			///<isolate each of these on its own cache line, via padding
		Head	mHead;
		//CacheLinePadding		pad2;			///<isolate each of these on its own cache line, via padding

    };
}

}// namespace Melting